// @algorithm @lc id=148 lang=cpp 
// @title sort-list


#define print(...)
// @test([4,2,1,3])=[1,2,3,4]
// @test([-1,5,3,4,0])=[-1,0,3,4,5]
// @test([])=[]
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(!head) return NULL;
        print("\nlist=", head, "\n")
        ListNode dummy(0, head), *cur = &dummy;
        int n = 0; while((cur = cur->next)) n++;
        for(int s=1; s<n; s<<=1){
            auto last = &dummy;
            cur = last->next;
            while(cur){
                auto h1 = cur;
                for(int i=1; i<s && cur->next; i++)
                    cur = cur->next;

                auto h2 = cur->next; cur->next = NULL; cur = h2;
                for(int i=1; i<s && cur; i++) cur = cur->next;
                ListNode* NEXT = NULL;
                if(cur){
                    NEXT = cur->next;
                    cur->next = NULL;
                }
                last->next = mergeTwoLists(h1, h2);
                while(last->next) last=last->next;
                cur = NEXT;
            }
        }
        print("ordered:", dummy.next, "\n")
        return dummy.next;
    }

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode emptyHead, *pre = &emptyHead;
    while(l1 && l2){
        auto s = (l1->val <= l2->val ? &l1 : &l2);
        pre->next = *s;
        pre = *s;
        *s = (*s)->next;
    }
    pre->next = (l1 ? l1 : l2);
    return emptyHead.next;
}
};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */